import java.util.Arrays;
import java.util.Random;

/**
 * @program: Session1Test
 * @description:
 * @author: Keyu Li
 * @create: 2021-09-18 21:33
 **/

public class SubArray {
    public static void main(String[] args) {
//        for (int i = 0; i < 10; i++) {
//            int[] array = createRandomArray(15);
//            System.out.println(Arrays.toString(array));
//            System.out.println(getMaxComplex(array) + ", " + getMaxSimple(array));
//        }

        int a;
        int[] array1 = {-15, -28, 31, 0, 49, -44, -22, -42, -36, -36, -30, -32, 21, -3, 46};
        System.out.println("操作前： " + Arrays.toString(array1));
        a = getMaxComplex(array1);
        int[] array2 = {0, 0, 47, -17, -22, 48, -6, 8, -37, 45, 15, 6, -19, 14, 3};
        System.out.println("操作前： " + Arrays.toString(array2));
        a = getMaxComplex(array2);
        int[] array3 = {36, 12, -11, 26, -17, -47, -47, 29, 0, 49, 32, -45, 40, -34, -40};
        System.out.println("操作前： " + Arrays.toString(array3));
        a = getMaxComplex(array3);
        int[] array4 = {-26, 24, -8, 21, -7, 26, 25, 9, -34, -22, -14, 19, -13, -7, -36};
        System.out.println("操作前： " + Arrays.toString(array4));
        a = getMaxComplex(array4);
        int[] array5 = {47, 36, -40, 32, -24, 44, -26, 19, 4, 0, 0, -4, 7, 1, 39};
        System.out.println("操作前： " + Arrays.toString(array5));
        a = getMaxComplex(array5);
    }

    static int getMaxSimple(int[] array) {
        int currentSum = array[0];
        int max = currentSum;
        for (int i = 1; i < array.length; i++) {
            if (currentSum < 0) {
                currentSum = array[i];
            } else
                currentSum += array[i];
            if (currentSum > max)
                max = currentSum;
        }
        return max;
    }

    static int getMaxComplex(int[] array) {
        int[] single = new int[array.length];
        boolean isNotPos = true;
        int sum = array[0];
        int count = 0;
        for (int i = 1; i < array.length; i++) {
            if (array[i] > 0) isNotPos = false;
            if (array[i] * array[i - 1] < 0) {
                array[count++] = sum;
                sum = array[i];
            } else if (array[i] * array[i - 1] > 0)
                sum += array[i];
            else {
                if (array[i - 1] == 0) {
                    sum += array[i];
                    continue;
                }
//                if (array[i - 1] > 0) {
//                    array[i] = 1;
//                    sum -= 1;
//                } else {
//                    array[i] = -1;
//                    sum += 1;
//                }
//                i--;
                array[i] = sum > 0 ? 1 : -1;
            }
        }
//        single[count++] = sum;
        array[count++] = sum;
        for (int i = count; i < array.length; i++) {
            array[i] = 0;
        }
        // 打印
        System.out.println("操作后： " + Arrays.toString(array));
        System.out.println("有效元素个数： " + count);

        if (single.length == 1) return single[0];
        if (isNotPos) {
            single = array;
            count = array.length;
        }
        int maxSub = single[0];
        int indexMax = 0;
        for (int i = 1; i < count; i++) {
            if (single[i] > maxSub) {
                maxSub = single[i];
                indexMax = i;
            }
        }
//        System.out.println(indexMax);
//        System.out.println(maxSub);
        if (isNotPos) return maxSub;
        int i = indexMax - 2;
        int j = indexMax + 2;
        boolean flagRun = true;
        while (flagRun) {
            if (i >= 0 && (single[i] + single[i + 1] > 0)) {
                maxSub += single[i] + single[i + 1];
                i -= 2;
            } else flagRun = false;
            if (j <= count - 1 && (single[j] + single[j - 1] > 0)) {
                maxSub += single[j] + single[j - 1];
                j += 2;
            } else flagRun = false;
        }
        return maxSub;
    }

    static int[] createRandomArray(int length) {
        Random random = new Random();
        int randValue;
        int sign;
        int[] array = new int[length];
        for (int i = 0; i < length; i++) {
            randValue = random.nextInt(50);
            sign = random.nextInt() % 2 == 0 ? -1 : 1;
            array[i] = randValue * sign;
        }
        return array;
    }
}


